class Solution:
    def integerReplacement(self, n: int) -> int:
        cnt = 0
        while n != 1:
            if n % 2 == 0:
                n //= 2
                cnt += 1
            elif n == 3:
                n -= 1
                cnt += 1
            elif n % 4 == 1:
                n -= 1
                cnt += 1
            else:
                n += 1
                cnt += 1
        return cnt

for i in range(1, 256):
    print(i, Solution().integerReplacement(i))
